#include <bits/stdc++.h>
using namespace std;

/*
837. 新 21 点
已解答
中等
相关标签
premium lock icon
相关企业
爱丽丝参与一个大致基于纸牌游戏 “21点” 规则的游戏，描述如下：

爱丽丝以 0 分开始，并在她的得分少于 k 分时抽取数字。 抽取时，她从 [1, maxPts] 的范围中随机获得一个整数作为分数进行累计，其中 maxPts 是一个整数。 每次抽取都是独立的，其结果具有相同的概率。

当爱丽丝获得 k 分 或更多分 时，她就停止抽取数字。

爱丽丝的分数不超过 n 的概率是多少？

与实际答案误差不超过 10-5 的答案将被视为正确答案。

 
示例 1：

输入：n = 10, k = 1, maxPts = 10
输出：1.00000
解释：爱丽丝得到一张牌，然后停止。
示例 2：

输入：n = 6, k = 1, maxPts = 10
输出：0.60000
解释：爱丽丝得到一张牌，然后停止。 在 10 种可能性中的 6 种情况下，她的得分不超过 6 分。
示例 3：

输入：n = 21, k = 17, maxPts = 10
输出：0.73278
 

提示：

0 <= k <= n <= 104
1 <= maxPts <= 104
*/

// 法一
class Solution {
public:
    double new21Game(int n, int k, int maxPts) {
        // 边界条件处理
        if (k == 0) return 1.0;   // 初始得0分就停止，必不超过n（n≥0）
        if (k > n)  return 0.0;   // 停止时至少得k分，而k>n，必超分
        if (n >= k + maxPts - 1) return 1.0;  // 最大可能得分k-1+maxPts ≤n，所有情况都有效

        // dp[i]：当前得分为i时，最终不超过n的概率（i范围0~n，因得分超n无意义）
        vector<double> dp(n + 1, 0.0);
        // 得分≥k时停止，若≤n则概率1.0（有效）
        for (int i = k; i <= n; ++i)            dp[i] = 1.0;

        // 初始窗口和：i=k-1时，抽牌后可能的得分范围是[k, k-1+maxPts]，取不超过n的部分
        double winSum = 0.0;
        int end = min(k + maxPts - 1, n);
        for (int i = k; i <= end; ++i)          winSum += dp[i];

        dp[k - 1] = winSum / maxPts;

        // 从k-2倒推到0，更新每个i的概率和滑动窗口
        for (int i = k - 2; i >= 0; --i) {
            // 窗口左移：加入dp[i+1]（原窗口左侧的下一个元素）
            winSum += dp[i + 1];
            // 窗口右移：移除超出当前窗口范围的元素（i+maxPts+1是原窗口右侧的超界元素）
            int outRange = i + maxPts + 1;
            if (outRange <= n) {
                winSum -= dp[outRange];
            }
            // 当前概率 = 窗口内概率和 / 抽牌可能数
            dp[i] = winSum / maxPts;
        }

        return dp[0];  // 初始得0分的概率就是答案
    }
};

// 法二
class Solution {
public:
    double new21Game(int n, int k, int maxPts) {
        // 边界条件：当k=0时，爱丽丝不抽牌，得分0，此时必不超过n（题目隐含n≥0），概率为1.0
        if (k == 0) {
            return 1.0;
        }
        
        // dp[i]表示当前得分为i时，最终得分不超过n的概率
        // 数组大小为k + maxPts，覆盖所有可能的得分：最大可能得分为k-1 + maxPts（最后一次抽牌前为k-1，抽maxPts）
        vector<double> dp(k + maxPts);
        
        // 初始化：当得分i≥k时停止抽牌，若i≤n则概率为1.0（有效）
        // 范围是[k, min(n, k+maxPts-1)]，超出n的部分概率为0（默认初始化为0）
        for (int i = k; i <= n && i < k + maxPts; i++) {
            dp[i] = 1.0;
        }
        
        // 计算k-1处的概率：此时抽牌后得分范围是[k, k-1+maxPts]
        // 有效得分（≤n）的数量为min(n - k + 1, maxPts)，每个概率均等，总概率为有效数量/maxPts
        dp[k - 1] = 1.0 * min(n - k + 1, maxPts) / maxPts;
        
        // 从k-2倒推至0，利用滑动窗口优化计算概率
        // 核心逻辑：dp[i] = (dp[i+1] + dp[i+2] + ... + dp[i+maxPts]) / maxPts
        // 优化后：dp[i] = dp[i+1] + (dp[i+1] - dp[i+maxPts+1])/maxPts
        // 推导：dp[i+1] = (dp[i+2] + ... + dp[i+maxPts+1])/maxPts
        // 两式相减得：dp[i] = (dp[i+1] * maxPts + dp[i+1] - dp[i+maxPts+1]) / maxPts
        // 化简为：dp[i] = dp[i+1] - (dp[i+maxPts+1] - dp[i+1]) / maxPts
        for (int i = k - 2; i >= 0; i--) {
            dp[i] = dp[i + 1] - (dp[i + maxPts + 1] - dp[i + 1]) / maxPts;
        }
        
        // 返回初始得分为0时的概率
        return dp[0];
    }
};